Transformacje
Limit pamięci: 128 MB
Dane są dwa słowa
i
złożone z liter a i b.
Naszym celem jest przekształcić słowo
w słowo
.
Mamy w tym celu do dyspozycji następującą operację zamiany:
wybieramy dwa rozłączne fragmenty ab i ba
w pierwszym słowie i zamieniamy je miejscami.
Czy, wykonując skończoną liczbę takich operacji, możemy przekształcić
w
?
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(
), oznaczającą długość słów.
Każdy z dwóch następnych wierszy zawiera ciąg złożony z
znaków a
i/lub b.
Pierwszy wiersz opisuje słowo
, a drugi - słowo
.
Możesz założyć, że słowa te będą różne.
Wyjście
W pierwszym wierszu wyjścia powinno znaleźć się jedno słowo TAK
lub NIE, oznaczające, czy słowo
można przekształcić
w słowo
, wykonując jedynie operacje zamiany.
Jeśli odpowiedź jest twierdząca oraz
,
Twój program powinien także wypisać przykładowy ciąg operacji
prowadzących do celu.
Pierwszy wiersz tego opisu powinien zawierać jedną liczbę całkowitą
(
), oznaczającą liczbę operacji.
Każdy z kolejnych
wierszy powinien zawierać dwie liczby całkowite
,
(
), oznaczające pozycje
pierwszych liter zamienianych fragmentów ab (odpowiednio
)
i ba (odpowiednio
).
Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien wypisać
jakiekolwiek z nich.
W szczególności Twoje rozwiązanie nie musi minimalizować liczby operacji,
tj. liczby
.
Przykład
Dla danych wejściowych:
6
aabbaa
baaaab
poprawną odpowiedzią jest:
TAK
2
2 4
1 5
natomiast dla danych:
6
aaabbb
ababab
poprawną odpowiedzią jest:
NIE
Autor zadania: Adam Polak.